googologywikiaorg-20200223-history
User blog:Rgetar/Three properties of standard forms
Any limit ordinal has infinite many fundamental sequences. Examples of fundamental sequences of ω: *0, 1, 2, 3, 4, 5, ... *8, 9, 10, 11, 12, 13, ... *0, 5, 10, 15, 20, 25, ... *1, 2, 4, 8, 16, 32, ... Sometimes it matters which fundamental sequence we choose, for example, in fast-growing hierarchy (FGH) fα(n) for limit α fα(n) = fαn(n) So, for different fundamental sequences of ω fω(n) are different functions: *fω(5) = f5(5) for 0, 1, 2, 3, 4, 5, ... *fω(5) = f13(5) for 8, 9, 10, 11, 12, 13, ... *fω(5) = f25(5) for 0, 5, 10, 15, 20, 25, ... *fω(5) = f32(5) for 1, 2, 4, 8, 16, 32, ... In such cases we need to choose a certain fundamental sequence for each limit ordinal (up to some large ordinal), that is define a system of fundamental sequences. So, we need *a notation of ordinals (up to some large ordinal) *algorithm of computation of any element of fundamental sequence of any ordinal expressed in this notation. Forms of ordinals An ordinal may be expressed in a given notation in different forms, for example, ε0 = ωε0 = ωωε0 = ωωωε0 = ωωωε0 = ωωωωε0 = ... Another example: Feferman–Schütte ordinal Γ0 expressed using Veblen function is *φ(1, 0, 0) But this is not only way to express Γ0 using Veblen function. Other ways: *φ(φ(1, 0, 0), 0) *φ(α, φ(1, 0, 0)), where α is any ordinal less than Γ0 and all possible combinations of these forms (that is replace "φ(1, 0, 0)" with another form of Γ0), for example, *φ(α1, φ(α2, φ(φ(α3, φ(α4, φ(φ(1, 0, 0), 0))), 0))), where α1, α2, α3, α4 < Γ0 Property #1 We can get different fundamental sequences of different forms of the same ordinal using the same algorithm. Example: ε0 = ωε0 and let our algorithm has rules: *for limit α ωαn = ωαn *ε00 = 0 *ε0n = ωε0- 1 for n > 0 So, for ε0 we get fundamental sequence 0, 1, ω, ωω, ωωω, ωωωω, ... and for ωε0 we get fundamental sequence 1, ω, ωω, ωωω, ωωωω, ωωωωω, ... It turns out that fε0(n) ≠ fωε0(n) despite ε0 = ωε0 And that's why we need standard forms. We need to say: "Let this form of ordinal in our notation is standard, and all other forms of this ordinal in our notation are non-standard", and then use only standard forms. Property #2 When we compute an element of fundamental sequence of standard form of an ordinal, using our algorithm, we can get a non-standard form. Example: let we have rules for standard forms *ε0 is standard form *ε0 + 1 is standard form *ωα is standard form, if α is not ε number, and α is in standard form and let we have rules for fundamental sequences *ωα + 1n = ωαn *for limit α ωαn = ωαn *ε00 = 0 *ε0n = ωε0- 1 for n > 0 ωε0 + 1 is standard form, and its fundamental sequence is 0, ωε0, ωε02, ωε03, ωε04, ωε05, ... So, we get ωε0 (non-standard form of ε0), despite given ordinal ωε0 + 1 was in standard form. So, fε0 + 1(1) = fωε0(1) = fω(1) = f1(1) = f0(1) = 1 + 1 = 2 which is not wrong (but it could be wrong). But should be fε0 + 1(1) = fε0(1) = f1(1) = f0(1) = 1 + 1 = 2 (Here it turned out that fω(1) = f1(1), but in general case fω(n) ≠ f1(n), so this could be an error). So, after computing element of fundamental sequence we need to convert it into standard form, because it may be in non-standard form. Property #3 If we use a function f(x) in our notation, then f(x) can be different for the same x in different forms. In ordinal notations sometimes functions are used. (Examples: Veblen function, ordinal collapsing functions). But if we convert x into standard form, then f(x) may be changed (despite x is not changed). Example: let α and β are different forms of the same ordinal ω: α = β = ω and α is standard form of ω, and β is non-standard form of ω. According "Property #1", we can get different fundamental sequences of α and β using the same algorithm. So, let fundamental sequence of α is 0, 2, 4, 6, 8, 10, ... and let fundamental sequence of β is 1, 3, 5, 7, 9, 11, ... Let f(x) is *f(0) = 0 *f(1) = ω + 1 *f(2) = 2 *f(3) = ω + 3 *f(4) = 4 *f(5) = ω + 5 *f(6) = 6 *f(7) = ω + 7 *f(8) = 8 *f(9) = ω + 9 *f(10) = 10 *f(11) = ω + 11 And let we have rule f(x)n = f(xn) for limit x So, f(α) = lim(f(α)0, f(α)1, f(α)2, f(α)3, f(α)4, f(α)5, ...) = lim(f(α0), f(α1), f(α2), f(α3), f(α4), f(α5), ...) = lim(f(0), f(2), f(4), f(6), f(8), f(10), ...) = lim(0, 2, 4, 6, 8, 10, ...) = ω f(β) = lim(f(β)0, f(β)1, f(β)2, f(β)3, f(β)4, f(β)5, ...) = lim(f(β0), f(β1), f(β2), f(β3), f(β4), f(β5), ...) = lim(f(1), f(3), f(5), f(7), f(9), f(11), ...) = lim(ω + 1, ω + 3, ω + 5, ω + 7, ω + 9, ω + 11, ...) = ω2 f(α) ≠ f(β) despite α = β = ω So, we should not convert into standard form parts of expression (such as arguments of functions), but only whole expression itself. In other words, converting into standard form should not be part of algoritmn of computing element of fundamental sequence, but it should be a separate algorithm, executed after computing element of fundamental sequence. Example: let we compute f(x)n. This is wrong way to compute f(x)n: *compute xn *convert xn into standard form *compute f(xn) *convert f(xn) into standard form And this is right way to compute f(x)n: *compute xn *compute f(xn) (even if xn is in non-standard form) *convert f(xn) into standard form Sometimes standard forms may contain non-standard forms, and we should not convert them into standard forms, otherwise we may get different ordinal. Category:Blog posts